package com.base.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName: BinaryTreePaths
 * @Description: 257. 二叉树的所有路径
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * @author: li
 * @Date: 2021/8/17 7:33 下午
 */
public class BinaryTreePaths {
    private class Path {
        /**
         * 不仅要保存当前结点，还要保存从根路径到当前结点的路径
         */
        TreeNode node;
        String path;

        public Path(TreeNode node, String path) {
            this.node = node;
            this.path = path;
        }
    }

    public List<String> binaryTreePaths(TreeNode root) {
        /**
         * 采用迭代的方法实现，每一个结点都要储存，根结点到它自身的路径大小。
         */
        List<String> res = new LinkedList<>();
        if (root == null) {
            return res;
        }


        Stack<Path> stack = new Stack<>();
        stack.add(new Path(root, Integer.toString(root.val)));
        while (!stack.isEmpty()) {
            Path cur = stack.pop();
            if (cur.node.left == null && cur.node.right == null) {
                res.add(cur.path);
            }
            if (cur.node.right != null) {
                stack.add(new Path(cur.node.right, cur.path + "->" + cur.node.right.val));
            }
            if (cur.node.left != null) {
                stack.add(new Path(cur.node.left, cur.path + "->" + cur.node.left.val));
            }

        }
        return res;

    }

    public List<String> binaryTreePaths1(TreeNode root) {
        /**
         * 基于递归的实现
         */
        List<String> paths = new ArrayList<>();
        if (root == null) {
            return paths;
        }
        dfs(paths, "", root);
        return paths;
    }

    private void dfs(List<String> paths, String path, TreeNode root) {
        if (root.left == null && root.right == null) {
            paths.add(path+ root.val);
            return;
        }else {
            path = path+ root.val +"->";
        }
        if (root.left != null) {
            dfs(paths, path , root.left);
        }
        if (root.right != null) {
            dfs(paths, path , root.right);
        }
    }


}
